SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

</head>

Cap set

</h1>

</header>

In <a href="Affine_geometry" title="Affine geometry">affine geometry</a>, a cap set is a subset of the affine space <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{3}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{3}^{n}}</annotation>

</semantics>

</math><img src="./78554d39bc961794db989618a32b8c28bdb1a37a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.769ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} _{3}^{n}}" loading="lazy"> (the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-dimensional <a href="Affine_space" title="Affine space">affine space</a> over the <a href="Finite_field" title="Finite field">three-element field</a>) where no three elements sum to the zero vector.

The cap set problem is the problem of finding the size of the largest possible cap set, as a function of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">.<a href="#cite_note-austin-1">[1]</a> The first few cap set sizes are 1, 2, 4, 9, 20, 45, 112, ... (sequence <a href="https://oeis.org/A090245" class="extiw external" title="oeis:A090245">A090245</a> in the <a href="On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>).

Caps are defined more generally as subsets of a finite affine or <a href="Projective_space" title="Projective space">projective space</a> with no three in a line.<a href="#cite_note-edel-2">[2]</a>

The "cap set" terminology should be distinguished from other unrelated mathematical objects with the same name, and in particular from sets with the compact absorption property in <a href="Function_space" title="Function space">function spaces</a><a href="#cite_note-3">[3]</a> as well as from compact convex co-convex subsets of a convex set.<a href="#cite_note-4">[4]</a>

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

An example of cap sets comes from the card game <a href="Set_(card_game)" title="Set (card game)">Set</a>, a card game in which each card has four features (its number, symbol, shading, and color), each of which can take one of three values. The cards of this game can be interpreted as representing points of the four-dimensional affine space <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{3}^{4}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{3}^{4}}</annotation>

</semantics>

</math><img src="./15d0c431ce676ca4330a7fb6fe83aa8f73f6d4f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.605ex; height:3.176ex;" alt="{\displaystyle \mathbb {Z} _{3}^{4}}" loading="lazy">, where each coordinate of a point specifies the value of one of the features. A line, in this space, is a triple of cards that, in each feature, are either all the same as each other or all different from each other. The game play consists of finding and collecting lines among the cards that are currently face up, and a cap set describes an array of face-up cards in which no lines may be collected.<a href="#cite_note-austin-1">[1]</a><a href="#cite_note-quanta-5">[5]</a><a href="#cite_note-bulletin-6">[6]</a>

One way to construct a large cap set in the game Set would be to choose two out of the three values for each feature, and place face up each of the cards that uses only one of those two values in each of its features. The result would be a cap set of 16 cards. More generally, the same strategy would lead to cap sets in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{3}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{3}^{n}}</annotation>

</semantics>

</math><img src="./78554d39bc961794db989618a32b8c28bdb1a37a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.769ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} _{3}^{n}}" loading="lazy"> of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation>

</semantics>

</math><img src="./8226f30650ee4fe4e640c6d2798127e80e9c160d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}" loading="lazy">. However, in 1970, Giuseppe Pellegrino proved that four-dimensional cap sets have maximum size 20.<a href="#cite_note-7">[7]</a> In terms of Set, this result means that some layouts of 20 cards have no line to be collected, but that every layout of 21 cards has at least one line. (The dates are not a typo: the Pellegrino cap set result from 1970 really does predate the first publication of the Set game in 1974.)<a href="#cite_note-8">[8]</a>

<div class="mw-heading mw-heading2"><h2 id="Maximum_size">Maximum size</h2></div>

Since the work of Pellegrino in 1971, and of <a href="Tom_Brown_(mathematician)" title="Tom Brown (mathematician)">Tom Brown</a> and Joe Buhler, who in 1984 proved that cap-sets cannot constitute any constant proportion of the whole space,<a href="#cite_note-Brown_214–220-9">[9]</a> there has been a significant line of research on how large they may be.

<div class="mw-heading mw-heading3"><h3 id="Lower_bounds">Lower bounds</h3></div>

Pellegrino's solution for the four-dimensional cap-set problem also leads to larger lower bounds than <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation>

</semantics>

</math><img src="./8226f30650ee4fe4e640c6d2798127e80e9c160d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}" loading="lazy"> for any higher dimension, which was further improved to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2.2173^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2.2173^{n}}</annotation>

</semantics>

</math><img src="./eb4e6ac3c4e1c6a87df40025e512814d876a0707.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.678ex; height:2.343ex;" alt="{\displaystyle 2.2173^{n}}" loading="lazy"> by <a href="#CITEREFEdel2004">Edel (2004)</a><a href="#cite_note-edel-2">[2]</a>

and then to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2.2180^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2.2180^{n}}</annotation>

</semantics>

</math><img src="./9476c792eaa9fed9c2747b89522ef18a942c7119.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.678ex; height:2.343ex;" alt="{\displaystyle 2.2180^{n}}" loading="lazy"> by <a href="#CITEREFTyrrell2022">Tyrrell (2022)</a>.<a href="#cite_note-tyrrell-10">[10]</a> In December 2023, a team of researchers from Google's DeepMind published a paper where they paired a <a href="Large_language_model" title="Large language model">large language model</a> (LLM) with an evaluator and managed to improve the bound to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2.2202^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2.2202^{n}}</annotation>

</semantics>

</math><img src="./05028575a7fefe8fa5aee444cd58a40e06eff15a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.678ex; height:2.343ex;" alt="{\displaystyle 2.2202^{n}}" loading="lazy">.<a href="#cite_note-11">[11]</a>

<div class="mw-heading mw-heading3"><h3 id="Upper_bounds">Upper bounds</h3></div>

In 1984, <a href="Tom_Brown_(mathematician)" title="Tom Brown (mathematician)">Tom Brown</a> and Joe Buhler<a href="#cite_note-Brown_214–220-9">[9]</a> proved that the largest possible size of a cap set in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{3}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{3}^{n}}</annotation>

</semantics>

</math><img src="./78554d39bc961794db989618a32b8c28bdb1a37a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.769ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} _{3}^{n}}" loading="lazy"> is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle o(3^{n})}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle o(3^{n})}</annotation>

</semantics>

</math><img src="./33e812106956a3f87e1ac2e4559523ef4ba674ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.318ex; height:2.843ex;" alt="{\displaystyle o(3^{n})}" loading="lazy"> as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> grows; loosely speaking, this means that cap sets have zero density. <a href="P%C3%A9ter_Frankl" title="Péter Frankl">Péter Frankl</a>, <a href="Ronald_Graham" title="Ronald Graham">Ronald Graham</a>, and <a href="Vojt%C4%9Bch_R%C3%B6dl" title="Vojtěch Rödl">Vojtěch Rödl</a> have shown<a href="#cite_note-12">[12]</a> in 1987 that the result of Brown and Buhler follows easily from the <a href="Imre_Z._Ruzsa" title="Imre Z. Ruzsa">Ruzsa</a> - <a href="Endre_Szemer%C3%A9di" title="Endre Szemerédi">Szemerédi</a> <a href="Triangle_removal_lemma" class="mw-redirect" title="Triangle removal lemma">triangle removal lemma</a>, and asked whether there exists a constant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c<3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c<3}</annotation>

</semantics>

</math><img src="./77e674ca077e620e509b5a1ca82ac5c2061094df.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;" alt="{\displaystyle c<3}" loading="lazy"> such that, indeed, for all sufficiently large values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, any cap set in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{3}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{3}^{n}}</annotation>

</semantics>

</math><img src="./78554d39bc961794db989618a32b8c28bdb1a37a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.769ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} _{3}^{n}}" loading="lazy"> has size at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c^{n}}</annotation>

</semantics>

</math><img src="./55d528e42c2910019e308d13c563e276abe0c809.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.225ex; height:2.343ex;" alt="{\displaystyle c^{n}}" loading="lazy">; that is, whether any set in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{3}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{3}^{n}}</annotation>

</semantics>

</math><img src="./78554d39bc961794db989618a32b8c28bdb1a37a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.769ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} _{3}^{n}}" loading="lazy"> of size exceeding <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c^{n}}</annotation>

</semantics>

</math><img src="./55d528e42c2910019e308d13c563e276abe0c809.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.225ex; height:2.343ex;" alt="{\displaystyle c^{n}}" loading="lazy"> contains an affine line. This question also appeared in a paper<a href="#cite_note-13">[13]</a> published by <a href="Noga_Alon" title="Noga Alon">Noga Alon</a> and Moshe Dubiner in 1995. In the same year, Roy Meshulam proved<a href="#cite_note-14">[14]</a> that the size of a cap set does not exceed <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\cdot 3^{n}/n}">

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\cdot 3^{n}/n}</annotation>

</semantics>

</math><img src="./49a466b310efb7957f1d2ea6e8239615c46a5fa3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.78ex; height:2.843ex;" alt="{\displaystyle 2\cdot 3^{n}/n}" loading="lazy">. Michael Bateman and <a href="Nets_Katz" title="Nets Katz">Nets Katz</a><a href="#cite_note-15">[15]</a> improved the bound to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(3^{n}/n^{1+\varepsilon })}">

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(3^{n}/n^{1+\varepsilon })}</annotation>

</semantics>

</math><img src="./ff035ec6e538ddb459a93f92783ac47f52a37634.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.62ex; height:3.176ex;" alt="{\displaystyle O(3^{n}/n^{1+\varepsilon })}" loading="lazy"> with a positive constant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \varepsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \varepsilon }</annotation>

</semantics>

</math><img src="./a30c89172e5b88edbd45d3e2772c7f5e562e5173.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.083ex; height:1.676ex;" alt="{\displaystyle \varepsilon }" loading="lazy">.

Determining whether Meshulam's bound can be improved to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c^{n}}</annotation>

</semantics>

</math><img src="./55d528e42c2910019e308d13c563e276abe0c809.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.225ex; height:2.343ex;" alt="{\displaystyle c^{n}}" loading="lazy"> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c<3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c<3}</annotation>

</semantics>

</math><img src="./77e674ca077e620e509b5a1ca82ac5c2061094df.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;" alt="{\displaystyle c<3}" loading="lazy"> was considered one of the most intriguing open problems in <a href="Arithmetic_combinatorics" title="Arithmetic combinatorics">additive combinatorics</a> and <a href="Ramsey_theory" title="Ramsey theory">Ramsey theory</a> for over 20 years, highlighted, for instance, by blog posts on this problem from <a href="Fields_Medal" title="Fields Medal">Fields medalists</a> <a href="Timothy_Gowers" title="Timothy Gowers">Timothy Gowers</a><a href="#cite_note-16">[16]</a> and <a href="Terence_Tao" title="Terence Tao">Terence Tao</a>.<a href="#cite_note-tao-17">[17]</a> In his blog post, Tao refers to it as "perhaps, my favorite open problem" and gives a simplified proof of the exponential bound on cap sets, namely that for any prime power <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy">, a subset <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S\subset F_{p}^{n}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S\subset F_{p}^{n}}</annotation>

</semantics>

</math><img src="./5a81db34903c192b1292e5b2934f678d951f2347.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.631ex; height:2.843ex;" alt="{\displaystyle S\subset F_{p}^{n}}" loading="lazy"> that contains no arithmetic progression of length <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 3}</annotation>

</semantics>

</math><img src="./991e33c6e207b12546f15bdfee8b5726eafbbb2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 3}" loading="lazy"> has size at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{p}^{n}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{p}^{n}}</annotation>

</semantics>

</math><img src="./f7dc802005f6e04ebc6aba574ea473fab8e1b5df.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.225ex; height:2.843ex;" alt="{\displaystyle c_{p}^{n}}" loading="lazy"> for some <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{p}<p}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{p}<p}</annotation>

</semantics>

</math><img src="./918770cd791382a8612f564d4aa51da252b1adaa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.334ex; height:2.509ex;" alt="{\displaystyle c_{p}<p}" loading="lazy">.<a href="#cite_note-tao-17">[17]</a>

The cap set conjecture was solved in 2016 due to a series of breakthroughs in the polynomial method. <a href="Ernest_S._Croot_III" title="Ernest S. Croot III">Ernie Croot</a>, Vsevolod Lev, and Péter Pál Pach posted a preprint on the related problem of progression-free subsets of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{4}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{4}^{n}}</annotation>

</semantics>

</math><img src="./2a6a2c26b1974882216cbf4217063a9caebde95d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.769ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} _{4}^{n}}" loading="lazy">, and the method was used by <a href="Jordan_Ellenberg" title="Jordan Ellenberg">Jordan Ellenberg</a> and Dion Gijswijt to prove an upper bound of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2.756^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2.756^{n}}</annotation>

</semantics>

</math><img src="./97665b17754064467dbb2f38f5be1b4bdc97ee42.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.515ex; height:2.343ex;" alt="{\displaystyle 2.756^{n}}" loading="lazy"> on the cap set problem.<a href="#cite_note-quanta-5">[5]</a><a href="#cite_note-bulletin-6">[6]</a><a href="#cite_note-18">[18]</a><a href="#cite_note-19">[19]</a><a href="#cite_note-20">[20]</a> In 2019, Sander Dahmen, Johannes Hölzl and Rob Lewis formalised the proof of this upper bound in the <a href="Lean_(proof_assistant)" title="Lean (proof assistant)">Lean theorem prover</a>.<a href="#cite_note-21">[21]</a>

As of March 2023, there is no exponential improvement to Ellenberg and Gijswijt's upper bound. Jiang showed that by precisely examining the multinomial coefficients that come out of Ellenberg and Gijswijt's proof, one can gain a factor of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\sqrt {n}}}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\sqrt {n}}}</annotation>

</semantics>

</math><img src="./2a2994734eae382ce30100fb17b9447fd8e99f81.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.331ex; height:3.009ex;" alt="{\displaystyle {\sqrt {n}}}" loading="lazy">.<a href="#cite_note-22">[22]</a> This saving occurs for the same reasons that there is a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {1/{\sqrt {n}}}}">

</mrow>

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {1/{\sqrt {n}}}}</annotation>

</semantics>

</math><img src="./226caf4528ea8d0dad56162dd9bc0236781c4448.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:5.656ex; height:3.009ex;" alt="{\displaystyle {1/{\sqrt {n}}}}" loading="lazy"> factor in the <a href="Central_binomial_coefficient" title="Central binomial coefficient">central binomial coefficient</a>.

<div class="mw-heading mw-heading2"><h2 id="Mutually_disjoint_cap_sets">Mutually disjoint cap sets</h2></div>

In 2013, five researchers together published an analysis of all the ways in which spaces of up to the size of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{3}^{4}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{3}^{4}}</annotation>

</semantics>

</math><img src="./15d0c431ce676ca4330a7fb6fe83aa8f73f6d4f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.605ex; height:3.176ex;" alt="{\displaystyle \mathbb {Z} _{3}^{4}}" loading="lazy"> can be partitioned into disjoint cap sets.<a href="#cite_note-disjoint-23">[23]</a> They reported that it is possible to use four different cap sets of size 20 in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} _{3}^{4}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} _{3}^{4}}</annotation>

</semantics>

</math><img src="./15d0c431ce676ca4330a7fb6fe83aa8f73f6d4f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.605ex; height:3.176ex;" alt="{\displaystyle \mathbb {Z} _{3}^{4}}" loading="lazy"> that between them cover 80 different cells; the single cell left uncovered is called the anchor of each of the four cap sets, the single point that when added to the 20 points of a cap set makes the entire sum go to 0 (mod 3). All cap sets in such a disjoint collection share the same anchor. Results for larger sizes are still open as of 2021.

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Sunflower_conjecture">Sunflower conjecture</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Sunflower_(mathematics)" title="Sunflower (mathematics)">Sunflower (mathematics)</a></div>

The solution to the cap set problem can also be used to prove a partial form of the <a href="Sunflower_(mathematics)" title="Sunflower (mathematics)">sunflower conjecture</a>, namely that if a family of subsets of an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">-element set has no three subsets whose pairwise intersections are all equal, then the number of subsets in the family is at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c^{n}}</annotation>

</semantics>

</math><img src="./55d528e42c2910019e308d13c563e276abe0c809.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.225ex; height:2.343ex;" alt="{\displaystyle c^{n}}" loading="lazy"> for a constant <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c<2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c<2}</annotation>

</semantics>

</math><img src="./46be8fcd4c84d3c5896cc6861e563bead56afc30.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.268ex; height:2.176ex;" alt="{\displaystyle c<2}" loading="lazy">.<a href="#cite_note-quanta-5">[5]</a><a href="#cite_note-24">[24]</a><a href="#cite_note-bulletin-6">[6]</a><a href="#cite_note-25">[25]</a>

<div class="mw-heading mw-heading3"><h3 id="Matrix_multiplication_algorithms">Matrix multiplication algorithms</h3></div>

The upper bounds on cap sets imply lower bounds on certain types of algorithms for <a href="Computational_complexity_of_matrix_multiplication#Group_theory_reformulation_of_matrix_multiplication_algorithms" title="Computational complexity of matrix multiplication">matrix multiplication</a>.<a href="#cite_note-26">[26]</a>

<div class="mw-heading mw-heading3"><h3 id="Strongly_regular_graphs">Strongly regular graphs</h3></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Games_graph" title="Games graph">Games graph</a></div>

The <a href="Games_graph" title="Games graph">Games graph</a> is a <a href="Strongly_regular_graph" title="Strongly regular graph">strongly regular graph</a> with 729 vertices. Every edge belongs to a unique triangle, so it is a <a href="Locally_linear_graph" title="Locally linear graph">locally linear graph</a>, the largest known locally linear strongly regular graph. Its construction is based on the unique 56-point cap set in the five-dimensional ternary <a href="Projective_space" title="Projective space">projective space</a> (rather than the affine space that cap-sets are commonly defined in).<a href="#cite_note-27">[27]</a>

<ul><li><a href="No-three-in-line_problem" title="No-three-in-line problem">No-three-in-line problem</a>, a problem of avoiding three elements in a line in a two-dimensional grid</li>

<li><a href="Ruzsa%E2%80%93Szemer%C3%A9di_problem" title="Ruzsa–Szemerédi problem">Ruzsa–Szemerédi problem</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFAustin2016" class="citation cs2">Austin, David (August 2016), <a rel="nofollow" class="external text" href="https://www.ams.org/samplings/feature-column/fc-2016-08">"Game. SET. Polynomial."</a>, Feature column, <a href="American_Mathematical_Society" title="American Mathematical Society">American Mathematical Society</a></cite>.

</li>

<li id="cite_note-edel-2">^ <a href="#cite_ref-edel_2-0">a</a> <a href="#cite_ref-edel_2-1">b</a> <cite id="CITEREFEdel2004" class="citation cs2">Edel, Yves (2004), "Extensions of generalized product caps", Designs, Codes and Cryptography, 31 (1): 5–14, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1023%2FA%3A1027365901231">10.1023/A:1027365901231</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2031694">2031694</a></cite>.

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> See, e.g., <cite id="CITEREFChapman1971" class="citation cs2">Chapman, T. A. (1971), "Dense sigma-compact subsets of infinite-dimensional manifolds", Transactions of the American Mathematical Society, 154: 399–426, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fs0002-9947-1971-0283828-7">10.1090/s0002-9947-1971-0283828-7</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0283828">0283828</a></cite>.

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> See, e.g., <cite id="CITEREFMinʹkova1979" class="citation cs2">Minʹkova, R. M. (1979), "Weak Korovkin spaces", Akademiya Nauk Soyuza SSR, 25 (3): 435–443, 477, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0534099">0534099</a></cite>.

</li>

<li id="cite_note-quanta-5">^ <a href="#cite_ref-quanta_5-0">a</a> <a href="#cite_ref-quanta_5-1">b</a> <a href="#cite_ref-quanta_5-2">c</a> <cite id="CITEREFKlarreich2016" class="citation cs2">Klarreich, Erica (May 31, 2016), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20161224083619/https://www.quantamagazine.org/20160531-set-proof-stuns-mathematicians/">"Simple Set Game Proof Stuns Mathematicians"</a>, Quanta, archived from <a rel="nofollow" class="external text" href="https://www.quantamagazine.org/20160531-set-proof-stuns-mathematicians/">the original</a> on December 24, 2016, retrieved August 2, 2016</cite>

</li>

<li id="cite_note-bulletin-6">^ <a href="#cite_ref-bulletin_6-0">a</a> <a href="#cite_ref-bulletin_6-1">b</a> <a href="#cite_ref-bulletin_6-2">c</a> <cite id="CITEREFGrochow2019" class="citation cs2">Grochow, Joshua A. (2019), "New applications of the polynomial method: The cap set conjecture and beyond", Bulletin of the American Mathematical Society, 56: 29–64, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fbull%2F1648">10.1090/bull/1648</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=3886143">3886143</a></cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFPellegrino1970" class="citation journal cs1 cs1-prop-foreign-lang-source">Pellegrino, Giuseppe (1970). <a rel="nofollow" class="external text" href="https://zbmath.org/0223.50020">"Sul massimo ordine delle calotte in \(S_4,3\)"</a> [The maximal order of the spherical cap in \(S_4,3\)]. Le Matematiche (in Italian). 25: 149–157. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0373-3505">0373-3505</a>.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFHill1983" class="citation cs2">Hill, R. (1983-01-01), Barlotti, A.; Ceccherini, P. V.; Tallini, G. (eds.), <a rel="nofollow" class="external text" href="https://www.sciencedirect.com/science/article/pii/S030402080873322X">"On Pellegrino's 20-Caps in S4, 3"</a>, North-Holland Mathematics Studies, Combinatorics '81 in honour of Beniamino Segre, vol. 78, North-Holland, pp. 433–447, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2FS0304-0208%2808%2973322-X">10.1016/S0304-0208(08)73322-X</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-444-86546-5</bdi>, retrieved 2023-12-16</cite>

</li>

<li id="cite_note-Brown_214–220-9">^ <a href="#cite_ref-Brown_214–220_9-0">a</a> <a href="#cite_ref-Brown_214–220_9-1">b</a> <cite id="CITEREFBrownBuhler1984" class="citation journal cs1"><a href="Tom_Brown_(mathematician)" title="Tom Brown (mathematician)">Brown, T. C</a>; Buhler, J. P (1984-03-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0097-3165%2884%2990006-2">"Lines imply spaces in density Ramsey theory"</a>. <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory</a>. Series A. 36 (2): 214–220. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0097-3165%2884%2990006-2">10.1016/0097-3165(84)90006-2</a>.</cite>

</li>

<li id="cite_note-tyrrell-10"><a href="#cite_ref-tyrrell_10-0">^</a> <cite id="CITEREFTyrrell2022" class="citation journal cs1">Tyrrell, Fred (2022). <a rel="nofollow" class="external text" href="https://discreteanalysisjournal.com/article/91076-new-lower-bounds-for-cap-sets">"New lower bounds for cap sets"</a>. Discrete Analysis. 2023 (20). <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2209.10045">2209.10045</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.19086%2Fda.91076">10.19086/da.91076</a> (inactive 11 July 2025). Retrieved 9 January 2024.</cite><code class="cs1-code">{{cite journal}}</code>: CS1 maint: DOI inactive as of July 2025 (link)

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFRomera-ParedesBarekatainNovikovBalog2023" class="citation journal cs1">Romera-Paredes, Bernardino; Barekatain, Mohammadamin; Novikov, Alexander; Balog, Matej; Kumar, M. Pawan; Dupont, Emilien; Ruiz, Francisco J. R.; Ellenberg, Jordan S.; Wang, Pengming; Fawzi, Omar; Kohli, Pushmeet; Fawzi, Alhussein (2023-12-14). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10794145">"Mathematical discoveries from program search with large language models"</a>. Nature. 625 (7995): 468–475. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1038%2Fs41586-023-06924-6">10.1038/s41586-023-06924-6</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1476-4687">1476-4687</a>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10794145">10794145</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/38096900">38096900</a>.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFFranklGrahamRödl1987" class="citation journal cs1"><a href="Peter_Frankl" title="Peter Frankl">Frankl, P.</a>; <a href="Ronald_Graham" title="Ronald Graham">Graham, R. L.</a>; <a href="Vojt%C4%9Bch_R%C3%B6dl" title="Vojtěch Rödl">Rödl, V.</a> (1987). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0097-3165%2887%2990053-7">"On subsets of abelian groups with no 3-term arithmetic progression"</a>. <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory</a>. Series A. 45 (1): 157–161. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0097-3165%2887%2990053-7">10.1016/0097-3165(87)90053-7</a>. <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0883900">0883900</a>.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite id="CITEREFAlonDubiner1995" class="citation journal cs1">Alon, Noga; Dubiner, Moshe (1995). "A lattice point problem and additive number theory". Combinatorica. 15 (3): 301–309. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01299737">10.1007/BF01299737</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0209-9683">0209-9683</a>.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFMeshulam1995" class="citation journal cs1">Meshulam, Roy (1995-07-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0097-3165%2895%2990024-1">"On subsets of finite abelian groups with no 3-term arithmetic progressions"</a>. <a href="Journal_of_Combinatorial_Theory" title="Journal of Combinatorial Theory">Journal of Combinatorial Theory</a>. Series A. 71 (1): 168–172. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0097-3165%2895%2990024-1">10.1016/0097-3165(95)90024-1</a>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFBatemanKatz2012" class="citation journal cs1">Bateman, Michael; Katz, Nets (2012-01-01). "New bounds on cap sets". Journal of the American Mathematical Society. 25 (2): 585–613. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1101.5851">1101.5851</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0894-0347-2011-00725-X">10.1090/S0894-0347-2011-00725-X</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0894-0347">0894-0347</a>.</cite>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://gowers.wordpress.com/2011/01/11/what-is-difficult-about-the-cap-set-problem/">"What is difficult about the cap-set problem?"</a>. Gowers's Weblog. 2011-01-11. Retrieved 2016-11-26.</cite>

</li>

<li id="cite_note-tao-17">^ <a href="#cite_ref-tao_17-0">a</a> <a href="#cite_ref-tao_17-1">b</a> <cite id="CITEREFTao2007" class="citation web cs1">Tao, Terence (2007-02-23). <a rel="nofollow" class="external text" href="https://terrytao.wordpress.com/2007/02/23/open-question-best-bounds-for-cap-sets/">"Open question: best bounds for cap sets"</a>. What's new. Retrieved 2016-11-26.</cite>

</li>

<li id="cite_note-18"><a href="#cite_ref-18">^</a> <cite class="citation cs2"><a rel="nofollow" class="external text" href="http://discreteanalysisjournal.com/post/45-an-exponential-upper-bound-for-the-cap-set-problem">"An exponential upper bound for the cap-set problem"</a>, Editorial, <a href="Discrete_Analysis" title="Discrete Analysis">Discrete Analysis</a>, June 5, 2016</cite>.

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite id="CITEREFCrootLevPach2017" class="citation cs2"><a href="Ernest_S._Croot_III" title="Ernest S. Croot III">Croot, Ernie</a>; Lev, Vsevolod; Pach, Peter (2017), "Progression-free sets in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Z_{4}^{n}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Z_{4}^{n}}</annotation>

</semantics>

</math><img src="./6f352a448d6462d55fd3d52cf78321d0a8cdb45d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.927ex; height:2.843ex;" alt="{\displaystyle Z_{4}^{n}}" loading="lazy"> are exponentially small", Annals of Mathematics, 185 (1): 331–337, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1605.01506">1605.01506</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2016arXiv160501506C">2016arXiv160501506C</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4007%2Fannals.2017.185.1.7">10.4007/annals.2017.185.1.7</a></cite>.

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <cite id="CITEREFEllenbergGijswijt2017" class="citation cs2"><a href="Jordan_Ellenberg" title="Jordan Ellenberg">Ellenberg, Jordan S.</a>; Gijswijt, Dion (2017), "On large subsets of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{q}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{q}^{n}}</annotation>

</semantics>

</math><img src="./0a630603c6f2f8f58f5d1fb9ef1b9ad194e258a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:2.639ex; height:3.176ex;" alt="{\displaystyle \mathbb {F} _{q}^{n}}" loading="lazy"> with no three-term arithmetic progression", <a href="Annals_of_Mathematics" title="Annals of Mathematics">Annals of Mathematics</a>, Second Series, 185 (1): 339–343, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1605.09223">1605.09223</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4007%2Fannals.2017.185.1.8">10.4007/annals.2017.185.1.8</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=3583358">3583358</a></cite>

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite id="CITEREFDahmenHölzlLewis2019" class="citation cs2">Dahmen, Sander R.; Hölzl, Johannes; Lewis, Robert Y. (2019), "Formalizing the solution to the cap set problem", in Harrison, John; O'Leary, John; Tolmach, Andrew (eds.), 10th International Conference on Interactive Theorem Proving, ITP 2019, September 9-12, 2019, Portland, OR, USA, LIPIcs, vol. 141, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 15:1–15:19, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1907.01449">1907.01449</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4230%2FLIPIcs.ITP.2019.15">10.4230/LIPIcs.ITP.2019.15</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-95977-122-1</bdi></cite>

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <cite id="CITEREFJiang2021" class="citation cs2">Jiang, Zhi (2021), Explicit Upper Bounds for the Cap Set Problem, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2103.06481">2103.06481</a></cite>

</li>

<li id="cite_note-disjoint-23"><a href="#cite_ref-disjoint_23-0">^</a> <cite id="CITEREFFollettKalailMcMahonPelland2014" class="citation cs2">Follett, Michael; Kalail, Kyle; McMahon, Elizabeth; Pelland, Catherine; Won, Robert (2014), "Partitions of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle AG(4,3)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle AG(4,3)}</annotation>

</semantics>

</math><img src="./2f090f36a36e88889c5d7c657b86cc1a7aa412a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.738ex; height:2.843ex;" alt="{\displaystyle AG(4,3)}" loading="lazy"> into maximal caps", <a href="Discrete_Mathematics_(journal)" title="Discrete Mathematics (journal)">Discrete Mathematics</a>, 337: 1–8, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1302.4703">1302.4703</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.disc.2014.08.002">10.1016/j.disc.2014.08.002</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=3262358">3262358</a></cite>

</li>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> <cite id="CITEREFHartnett2019" class="citation web cs1">Hartnett, Kevin (21 October 2019). <a rel="nofollow" class="external text" href="https://www.quantamagazine.org/mathematicians-begin-to-tame-wild-sunflower-problem-20191021/">"Mathematicians Begin to Tame Wild 'Sunflower' Problem"</a>. Quanta Magazine. Retrieved 2019-10-22.</cite>

</li>

<li id="cite_note-25"><a href="#cite_ref-25">^</a> <cite id="CITEREFKalai2016" class="citation cs2"><a href="Gil_Kalai" title="Gil Kalai">Kalai, Gil</a> (May 17, 2016), <a rel="nofollow" class="external text" href="https://gilkalai.wordpress.com/2016/05/17/polymath-10-emergency-post-5-the-erdos-szemeredi-sunflower-conjecture-is-now-proven/">"Polymath 10 Emergency Post 5: The Erdos-Szemeredi Sunflower Conjecture is Now Proven"</a>, Combinatorics and more</cite>.

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> <cite id="CITEREFBlasiakChurchCohnGrochow2016" class="citation cs2">Blasiak, Jonah; Church, Thomas; Cohn, Henry; Grochow, Joshua A.; <a href="Chris_Umans" title="Chris Umans">Umans, Chris</a> (2016), "On cap sets and the group-theoretic approach to matrix multiplication", Discrete Analysis, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1605.06702">1605.06702</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2016arXiv160506702B">2016arXiv160506702B</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.19086%2Fda.1245">10.19086/da.1245</a></cite>.

</li>

<li id="cite_note-27"><a href="#cite_ref-27">^</a> <cite id="CITEREFHill1978" class="citation cs2">Hill, Raymond (1978), "Caps and codes", <a href="Discrete_Mathematics_(journal)" title="Discrete Mathematics (journal)">Discrete Mathematics</a>, 22 (2): 111–137, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0012-365X%2878%2990120-6">10.1016/0012-365X(78)90120-6</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0523299">0523299</a></cite>.

</li>

</ol></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-11" href="https://en.wikipedia.org/wiki/?title=Cap_set&oldid=1300026154">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>